package datastructure.book.tujiesuanfa.order._1_all;

import datastructure.book.tujiesuanfa.list.bean.ListNode;
import org.junit.jupiter.api.Test;

public class Solution {

    @Test
    public void testSortList(){
        ListNode node9 = new ListNode(9);
        ListNode node8 = new ListNode(8,node9);
        ListNode node5 = new ListNode(5,node8);
        ListNode node7 = new ListNode(7,node5);
        ListNode node1 = new ListNode(1,node7);
        ListNode node2 = new ListNode(2,node1);
        ListNode node6 = new ListNode(6,node2);
        ListNode node3 = new ListNode(3,node6);
        ListNode node4 = new ListNode(4,node3);
        System.out.println(sortList(node4));
    }
    /**
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * 4->3->6->2->1->7->5->8->9
     * 1->2->3->4->5->6->7->8->9
     */
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        int len = this.getListLength(head);
        ListNode result = new ListNode(0,head);
        int i = 1;
        while (i < len) {
            ListNode preNode = null;
            ListNode nextHead = result.next;
            while (nextHead != null) {
                ListNode leftHead = nextHead;
                ListNode[] indexNode = getIndexNode(leftHead,i);
                ListNode rightHead = indexNode[0];
                nextHead = indexNode[1];
                if (rightHead == null) {
                    preNode.next = leftHead;
                    break;
                }
                ListNode[] mergedList = merge(leftHead, rightHead);
                if (preNode == null) {
                    result.next = mergedList[0];
                    preNode = mergedList[1];
                } else {
                    preNode.next = mergedList[0];
                    preNode = mergedList[1];
                }
            }
            i*=2;
        }
        return result.next;
    }

    private ListNode[] merge(ListNode leftHead, ListNode rightHead) {
        ListNode head = new ListNode();
        ListNode pre = null;
        while (leftHead != null || rightHead != null) {
            if (leftHead == null) {
                pre.next = rightHead;
                while (pre.next != null) {
                    pre = pre.next;
                }
                break;
            }
            if (rightHead == null) {
                pre.next = leftHead;
                while (pre.next != null) {
                    pre = pre.next;
                }
                break;
            }
            if (leftHead.val > rightHead.val) {
                if (pre == null) {
                    head.next = rightHead;
                    pre = rightHead;
                } else {
                    pre.next = rightHead;
                    pre = pre.next;
                }
                rightHead = rightHead.next;
            } else {
                if (pre == null) {
                    head.next = leftHead;
                    pre = leftHead;
                } else {
                    pre.next = leftHead;
                    pre = pre.next;
                }
                leftHead = leftHead.next;
            }
        }
        return new ListNode[]{head.next,pre};
    }

    private ListNode[] getIndexNode(ListNode head, int i) {
        ListNode[] indexNode = new ListNode[2];
        for (int j = 0; j < i-1; j++) {
            if (head != null) {
                head = head.next;
            } else {
                break;
            }
        }
        if (head == null) {
            return indexNode;
        }
        indexNode[0] = head.next;
        head.next = null;
        ListNode rightHead = indexNode[0];
        for (int j = 0; j < i-1; j++) {
            if (rightHead != null) {
                rightHead = rightHead.next;
            } else {
                break;
            }
        }
        if (rightHead != null) {
            indexNode[1] = rightHead.next;
            rightHead.next = null;
        }
        return indexNode;
    }

    private int getListLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}
